다차원 공간 분할 자료구조의 비교

1. 서론

1.1 공간 분할의 필요성 및 중요성

3차원 공간 데이터를 효율적으로 저장, 검색, 그리고 관리하는 기술은 현대 컴퓨터 과학의 여러 분야에서 핵심적인 과제로 자리 잡았다. 컴퓨터 그래픽스, 로봇 공학, 지리 정보 시스템(GIS), 자율 주행, 물리 시뮬레이션, 그리고 가상현실에 이르기까지, 방대한 양의 공간 정보를 실시간으로 처리하는 능력은 응용 프로그램의 성능과 직결된다. 이러한 데이터는 수백만 개에서 수십억 개에 이르는 점(point)이나 복셀(voxel)로 구성될 수 있으며, 이를 단순한 선형 배열에 저장하고 필요한 정보를 찾기 위해 순차적으로 탐색하는 소박한(naive) 접근법은 데이터의 양이 증가함에 따라 기하급수적으로 비효율적이 된다. 예를 들어, 특정 지점의 최근접 이웃(nearest neighbor)을 찾거나 특정 범위 내의 모든 점을 찾는 질의는 데이터셋의 모든 원소를 검사해야 하므로, 데이터의 개수가 N일 때 각각 O(N) 또는 O(N^2)의 시간 복잡도를 가지게 된다.1 이는 대규모 데이터셋에서는 실용적으로 사용될 수 없는 수준의 비효율성이다.

이러한 근본적인 한계를 극복하기 위해 공간 분할(Spatial Partitioning) 자료구조가 개발되었다. 공간 분할 자료구조의 핵심 철학은 거대한 탐색 공간을 관리하기 쉬운 작은 부분 공간으로 계층적으로 또는 균일하게 나누는 데 있다.1 공간을 분할함으로써, 특정 질의와 관련 없는 대부분의 데이터 영역을 탐색 과정에서 배제(pruning)할 수 있다. 이 원리를 통해 탐색 연산의 시간 복잡도를 평균적으로 로그 시간(O(logN))이나 경우에 따라서는 거의 상수 시간(O(1))에 가깝게 단축시킬 수 있으며, 이는 대규모 3차원 데이터의 실시간 처리를 가능하게 하는 핵심 기술이다.1

1.2 안내서의 목적과 분석 대상

본 안내서는 점 데이터(point data)부터 희소(sparse) 및 밀집(dense) 복셀 데이터에 이르기까지 다양한 유형의 3차원 공간 데이터를 처리하기 위해 지난 수십 년간 제안되고 발전해 온 핵심적인 공간 분할 자료구조들을 심층적으로 비교하고 고찰하는 것을 목적으로 한다. 분석 대상은 학계와 산업계에서 중요하게 다루어지는 10가지 자료구조로, 다음과 같다:

1. kd-tree (k-차원 트리)
2. i-kd-tree (증분 k-차원 트리)
3. Octree (옥트리)
4. Sparse Voxel Octree (SVO, 희소 복셀 옥트리)
5. Sparse Voxel Directed Acyclic Graph (SVDAG, 희소 복셀 방향성 비순환 그래프)
6. 동적 균형 Octree (Dynamic Balanced Octree)
7. iVox (증분 복셀)
8. iVox-PHC (유사 힐버트 곡선 기반 증분 복셀)
9. RC-Vox (로봇 중심 복셀 맵)
10. VDB (Volumetric Dynamic B+Tree)

본 안내서는 각 자료구조의 단순한 기능적 설명을 넘어, 그 기저에 깔린 수학적 원리와 알고리즘적 특성, 성능상의 장단점, 그리고 특정 응용 분야에 적합하게 된 진화적 맥락을 깊이 있게 파헤칠 것이다.

1.3 안내서의 구조

안내서는 독자의 이해를 돕기 위해 논리적 흐름에 따라 구성된다. 먼저 가장 기초가 되는 점 기반 공간 분할 구조인 kd-tree와 Octree를 분석하여 공간 분할의 두 가지 근본적인 접근법을 제시한다. 이후, 컴퓨터 그래픽스와 시각 효과(VFX) 분야에서 대두된 메모리 효율성 문제를 해결하기 위해 등장한 고도로 압축된 복셀 구조인 SVO, SVDAG, VDB를 다룬다. 다음으로, 로보틱스와 자율 주행 분야의 실시간 요구사항을 충족시키기 위해 극단적인 동적 업데이트 성능에 초점을 맞춰 발전한 동적 균형 Octree, iVox, RC-Vox를 분석한다.

각 자료구조에 대해 핵심 원리, 주요 연산 알고리즘, 시간 및 공간 복잡도, 그리고 주요 응용 분야를 상세히 기술한다. 마지막 장에서는 이 모든 분석을 종합하여, 10가지 자료구조의 성능과 특성을 다각적으로 비교하는 종합 표를 제시하고, 메모리 압축과 동적 업데이트 속도라는 두 가지 핵심 축을 기준으로 자료구조들을 그룹화하여 심층 분석한다. 최종적으로, 특정 응용 시나리오에 가장 적합한 자료구조를 선택할 수 있도록 실용적인 가이드라인을 제공하며 안내서를 마무리한다.

2. 기초적인 공간 분hal 구조

공간 분할 자료구조의 세계를 이해하기 위해서는 가장 근본이 되는 두 가지 구조, 즉 kd-트리와 옥트리에 대한 깊이 있는 이해가 선행되어야 한다. 이 두 구조는 공간을 분할하는 방식에서 근본적인 차이를 보이며, 이후에 등장하는 수많은 파생 및 고급 자료구조들의 사상적 기반을 형성한다. 본 장에서는 이 두 기초적인 구조의 원리, 성능 특성, 그리고 그 변형들을 상세히 분석한다.

2.1 k-차원 트리 (k-d Tree)

k-d 트리는 다차원 공간에서의 점 데이터를 효율적으로 구성하고 검색하기 위해 설계된 가장 대표적인 공간 분할 자료구조 중 하나이다.

2.1.1 핵심 원리

k-d 트리(k-dimensional tree)는 k-차원 공간에 분포된 점들을 저장하기 위한 이진 공간 분할(Binary Space Partitioning, BSP) 트리의 한 종류이다.4 k-d 트리의 각 비-리프 노드(non-leaf node)는 하나의 k-차원 점 데이터를 저장하며, 이 점을 통과하고 특정 축(axis)에 수직인 초평면(hyperplane)을 기준으로 공간을 두 개의 하위 공간(half-space)으로 분할한다.5 이 분할 기준이 되는 축을 ’판별자(discriminator)’라고 부르며, 일반적으로 트리의 깊이(depth)에 따라 각 차원을 순환적으로 선택한다.6 예를 들어, 3차원 공간에서는 루트 노드에서 x축, 그 자식 노드들에서 y축, 손자 노드들에서 z축, 그리고 다시 x축으로 순환하는 방식이 널리 사용된다.8

이러한 분할 방식의 가장 중요한 특징은 분할 경계가 저장된 데이터의 분포에 따라 결정된다는 점이다. 즉, k-d 트리는 데이터 종속적(data-dependent) 분할 방식을 채택한다.9 이는 데이터가 밀집된 영역은 더 세밀하게, 희소한 영역은 더 넓게 분할하여 데이터 분포에 적응적인 공간 분할을 가능하게 한다.

2.1.2 구축 및 주요 연산

k-d 트리의 성능은 트리의 균형 상태에 크게 좌우되며, 주요 연산은 다음과 같다.

• 구축 (Construction): 정적 k-d 트리를 구축하는 가장 일반적인 방법은 각 레벨에서 해당 분할 축을 기준으로 점들의 중앙값(median)을 찾아 피벗(pivot)으로 삼는 것이다. 이 피벗 점을 현재 노드에 저장하고, 피벗보다 작은 값들을 갖는 점들은 왼쪽 서브트리로, 큰 값들을 갖는 점들은 오른쪽 서브트리로 보내는 과정을 재귀적으로 반복한다.4 중앙값을 사용하면 각 분할에서 점들이 거의 절반씩 나뉘므로, 결과적으로 깊이가 O(\log N)에 가까운 비교적 균형 잡힌 트리를 생성할 수 있다. 매 레벨에서 중앙값을 찾기 위해 정렬을 사용하면 구축 시간 복잡도는 O(N \log^2 N)이 되며, 선형 시간 중앙값 찾기 알고리즘(median of medians)을 사용하면 O(N \log N)으로 최적화할 수 있다.5

• 탐색 (Search): 특정 점을 찾는 탐색 연산은 이진 탐색 트리(BST)와 매우 유사하다. 루트 노드부터 시작하여, 현재 노드의 깊이에 해당하는 분할 축 값을 기준으로 찾고자 하는 점의 좌표와 노드의 좌표를 비교한다. 찾고자 하는 점의 값이 노드의 값보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동하는 과정을 반복한다.4 균형 잡힌 트리에서의 평균 탐색 시간 복잡도는 O(\log N)이다.11

• 삽입 및 삭제 (Insertion and Deletion): 새로운 점의 삽입은 탐색과 유사한 과정을 통해 적절한 위치를 찾아 리프 노드로 추가하는 방식으로 이루어진다. 평균 시간 복잡도는 O(\log N)이다.4 그러나 반복적인 삽입은 트리의 불균형을 초래하여 최악의 경우 성능을 O(N)으로 저하시킬 수 있다. 삭제 연산은 더 복잡하다. 삭제할 노드가 리프 노드이면 간단히 제거할 수 있지만, 내부 노드일 경우 해당 노드의 서브트리에서 적절한 대체 노드(예: 해당 분할 축 기준의 최소값)를 찾아 그 자리를 메우고, 대체 노드를 원래 위치에서 삭제하는 과정이 필요하다. 이 과정은 서브트리의 구조를 유지해야 하므로 복잡하며, 균형을 유지하기 위한 추가적인 재구성 작업이 필요할 수 있다.4 균형이 잘 잡힌 트리에서의 삭제 연산은 평균적으로 O(\log N)의 시간 복잡도를 가진다.5

• 최근접 이웃(k-NN) 및 반경 탐색 (Range Search): k-d 트리의 가장 강력하고 핵심적인 응용 분야는 최근접 이웃 탐색(k-Nearest Neighbors, k-NN)과 반경 탐색(Range Search)이다.5

• k-NN 탐색: 특정 질의점(query point)에 가장 가까운 k개의 점을 찾는 연산이다. 먼저 일반적인 탐색 방식으로 질의점이 속할 리프 노드까지 내려간다. 이후, 재귀적으로 부모 노드로 거슬러 올라가는 백트래킹(backtracking) 과정을 수행한다. 각 노드에서, 현재까지 찾은 가장 가까운 점과의 거리를 반지름으로 하는 구(hypersphere)와 현재 노드의 분할 평면이 교차하는지 확인한다. 만약 교차한다면, 분할 평면 반대편의 서브트리에도 더 가까운 점이 존재할 가능성이 있으므로 해당 서브트리를 추가로 탐색한다. 이 과정을 통해 탐색 공간을 효율적으로 가지치기(pruning)할 수 있다. 평균 시간 복잡도는 O(\log N)이지만, 데이터의 차원이 높아질수록 성능이 저하된다.5

• 반경 탐색: 특정 질의점을 중심으로 주어진 반경 내에 포함되는 모든 점을 찾는 연산이다. k-NN 탐색과 유사하게, 질의 구와 노드가 나타내는 공간 영역이 교차하는 경우에만 해당 서브트리를 탐색한다. 3차원 데이터의 경우, 시간 복잡도는 O(N^{2/3} + m)으로 알려져 있으며, 여기서 m은 반경 내에 발견된 점의 수이다.5 이 복잡도 공식은 k-d 트리가 ’차원의 저주(curse of dimensionality)’에 취약함을 보여준다. 즉, 차원

k가 증가할수록 성능이 지수적으로 저하되어 고차원 공간에서는 선형 탐색과 다를 바 없어질 수 있다.

2.1.3 i-kd-tree (증분 kd-트리, Incremental k-d Tree)

정적인 k-d 트리는 데이터셋이 변하지 않는 경우에 효과적이지만, 점의 삽입과 삭제가 빈번하게 발생하는 동적 환경에서는 심각한 성능 저하를 겪을 수 있다. 반복적인 삽입과 삭제는 트리의 균형을 깨뜨려 깊이가 비정상적으로 길어지게 만들고, 이는 탐색 성능을 최악의 경우 선형 시간(O(N))으로 떨어뜨린다. 이러한 문제를 해결하기 위해 등장한 것이 **i-kd-tree (incremental k-d tree)**이다.

i-kd-tree는 특히 실시간 LiDAR SLAM(Simultaneous Localization and Mapping)과 같은 응용 분야에서 그 중요성이 부각되었다. 예를 들어, Fast-LIO2 시스템에서는 주변 환경을 매핑하기 위해 지속적으로 들어오는 LiDAR 포인트 클라우드를 처리해야 하는데, 매 스캔마다 전체 k-d 트리를 재구축하는 것은 엄청난 계산 비용을 유발한다.13 i-kd-tree는 이러한 비효율성을 해결한다.

핵심 메커니즘은 전체 재구축을 피하고, 삽입 또는 삭제 연산이 발생했을 때 트리의 균형을 동적으로 유지하는 것이다. 이는 특정 서브트리의 크기나 깊이가 임계값을 초과하면 해당 서브트리만 재귀적으로 재구축하는 부분 재구축(partial rebuilding) 기법이나, 트리 회전(tree rotation)과 유사한 기법을 통해 구현될 수 있다. 이러한 증분 업데이트(incremental update) 방식을 통해, i-kd-tree는 동적인 데이터 변화 속에서도 트리의 깊이를 O(logN) 수준으로 유지하며, 삽입, 삭제, 검색 연산의 평균 시간 복잡도를 로그 시간으로 보장한다. 이는 실시간 응용에서 필수적인 빠른 업데이트 속도와 꾸준한 검색 성능을 동시에 만족시키는 핵심적인 역할을 한다.14

2.1.4 i-kd-tree의 변형: Implicit k-d tree

k-d 트리의 또 다른 흥미로운 변형은 Implicit k-d tree이다. 이 구조는 k-d 트리의 위상(topology), 즉 분할 평면의 위치와 방향을 메모리에 명시적으로 저장하지 않는다.5 대신, 기저에 깔린 정형 격자(rectilinear grid) 위에서 사전에 정의된 재귀적인 분할 함수(splitting function)를 통해 암시적으로(implicitly) 트리를 정의한다.15

예를 들어, ’격자 중앙값 분할 함수(grid median splitting-function)’는 각 노드에 해당하는 하이퍼 사각형(hyperrectangle) 영역에서 가장 긴 축을 분할 축으로 선택하고, 해당 축의 격자 중앙에 가장 가까운 격자 평면을 분할 평면으로 결정한다.15 이처럼 노드를 방문할 때마다 분할 함수를 호출하여 필요한 분할 정보를 동적으로 계산한다.

이 방식의 가장 큰 장점은 메모리 효율성이다. 명시적인 포인터나 분할 값 저장이 필요 없으므로, 데이터 자체를 저장하는 격자 외에 아주 적은 추가 메모리만으로 k-d 트리의 가속 구조를 활용할 수 있다.15 이러한 특성 덕분에 Implicit k-d tree는 대규모 스칼라 필드 데이터(예: 의료 영상, 과학 시뮬레이션 데이터)의 등가곡면(isosurface) 렌더링이나 최대 강도 투사(Maximum Intensity Projection, MIP)와 같은 시각화 응용에서 매우 효과적으로 사용된다. 광선(ray)이 공간을 통과할 때, 각 노드에 미리 계산된 속성(예: 해당 영역의 최대/최소 스칼라 값)을 이용하여 관심 없는 영역을 통째로 건너뛸 수 있어 렌더링 속도를 크게 향상시킨다.15

2.2 옥트리 (Octree)

옥트리는 3차원 공간을 분할하는 가장 직관적이고 널리 사용되는 계층적 자료구조 중 하나로, k-d 트리와는 다른 분할 철학을 가지고 있다.

2.2.1 핵심 원리

옥트리(Octree)는 3차원 공간을 나타내는 정육면체 형태의 루트 노드(root node)에서 시작하여, 공간을 재귀적으로 8개의 동일한 크기를 가진 자식 정육면체, 즉 **옥턴트(octant)**로 분할하는 자료구조이다.19 이 분할은 항상 노드의 중심점을 지나고 각 좌표축(x, y, z)에 평행한 세 개의 평면에 의해 이루어진다.19 분할 과정은 특정 조건을 만족할 때까지 계속된다. 예를 들어, 노드 내에 포함된 데이터의 수가 특정 임계값 이하가 되거나, 노드의 크기가 최소 단위에 도달하거나, 노드가 완전히 비어있거나 완전히 채워져 있을 때 분할을 멈추고 해당 노드는 리프 노드(leaf node)가 된다.

k-d 트리가 데이터의 분포에 따라 분할 경계를 유연하게 결정하는 ‘데이터 종속적’ 방식인 것과 대조적으로, 옥트리는 데이터의 내용과 무관하게 항상 공간을 기하학적으로 균등하게 8등분한다. 이러한 특성 때문에 옥트리는 공간 주도적(space-driven) 분할 방식의 대표적인 예로 꼽힌다.

2.2.2 구조 및 주요 연산

• 구조: 옥트리는 루트 노드가 전체 공간을 포함하고, 각 내부 노드는 8개의 자식 노드에 대한 포인터(또는 인덱스)를 가지는 트리 구조를 형성한다. 리프 노드는 더 이상 분할되지 않는 최소 단위의 공간 또는 해당 공간에 포함된 데이터 목록을 저장한다.20 이 계층적 구조는 공간의 밀도에 따라 트리의 깊이가 적응적으로 달라지게 한다. 즉, 객체가 밀집된 복잡한 영역은 깊은 레벨까지 분할되고, 비어있는 넓은 영역은 얕은 레벨의 큰 노드로 표현되어 효율적인 공간 표현이 가능하다.20
• 탐색 및 질의:
• 점 위치 질의(Point Location): 특정 좌표가 어느 리프 노드에 속하는지 찾는 연산은 매우 간단하다. 루트 노드에서 시작하여, 해당 점이 8개의 자식 옥턴트 중 어디에 포함되는지 계산하고 해당 자식 노드로 이동하는 과정을 리프 노드에 도달할 때까지 재귀적으로 반복한다.22
• 반경 탐색(Radius Search): 특정 지점을 중심으로 하는 구(sphere)와 교차하는 모든 데이터를 찾는 질의이다. 옥트리는 이 연산을 효율적으로 처리할 수 있다. 루트에서부터 시작하여, 질의 구가 현재 노드의 경계 상자(bounding box)와 교차하는지 검사한다. 만약 교차하지 않으면, 해당 노드의 모든 하위 트리는 탐색에서 제외된다. 교차하는 경우에만 자식 노드들로 재귀적으로 탐색을 계속 진행한다. 이 가지치기(pruning) 과정을 통해 탐색 범위를 크게 줄일 수 있다.19
• 장점: 옥트리의 가장 큰 장점은 구조가 규칙적이고 개념적으로 단순하여 구현이 비교적 용이하다는 점이다. 또한, 공간의 복잡도에 따라 분할 깊이를 조절하는 적응적 특성 덕분에 다양한 밀도를 가진 데이터를 효율적으로 표현할 수 있다. 이는 컴퓨터 그래픽스의 충돌 감지, 가시성 컬링(visibility culling), 그리고 복셀 데이터 렌더링 등 다양한 분야에서 널리 활용되는 이유이다.20

2.2.3 kd-트리와의 비교

k-d 트리와 옥트리는 공간 분할이라는 동일한 목표를 가지지만, 그 접근 방식의 차이로 인해 성능과 특성에서 뚜렷한 차이를 보인다. 이 둘의 비교는 공간 분할 자료구조 설계의 핵심적인 트레이드오프를 보여준다.

• 분할 방식의 근본적 차이: 앞서 언급했듯이, k-d 트리는 데이터 종속적으로 분할 경계를 설정하는 반면, 옥트리는 공간 주도적으로 고정된 분할을 수행한다. 이로 인해 데이터가 특정 영역에 심하게 몰려있는 비균일 분포(non-uniform distribution)의 경우, k-d 트리는 데이터가 없는 넓은 공간을 하나의 큰 노드로 남겨두고 밀집 지역만 세밀하게 분할하여 더 효율적이고 균형 잡힌 트리를 만들 수 있다.9 반면, 옥트리는 데이터 유무와 상관없이 공간을 균등하게 나누기 때문에, 비어있는 공간에도 불필요한 분할을 수행하거나, 매우 밀집된 클러스터 전체가 하나의 거대한 리프 노드에 포함되어 분할의 이점을 잃을 수 있다.1
• 질의 성능 비교:
• k-NN 탐색: 여러 실험 결과에 따르면, k-NN 탐색에서는 일반적으로 k-d 트리가 옥트리보다 우수한 성능을 보인다. PCL(Point Cloud Library)을 이용한 한 비교 실험에서는, 동일한 데이터셋에 대한 k-NN 탐색(k=1, 10, 100)에서 k-d 트리가 옥트리보다 약 3배에서 4.5배까지 빠른 것으로 나타났다.12 이는 k-d 트리의 데이터 적응적 분할이 탐색 공간을 더욱 효과적으로 가지치기하기 때문으로 분석된다.
• 반경 탐색: 반면, 반경 탐색(radius search)에서는 옥트리가 더 나은 성능을 보이는 경우가 많다. 위와 동일한 실험에서, 반경 탐색은 옥트리가 k-d 트리보다 월등히(약 5배에서 14배) 빠른 결과를 보였다.12 이는 옥트리의 규칙적이고 예측 가능한 분할 구조 덕분에 질의 구와 교차하는 노드를 판단하는 것이 더 간단하고 빠르기 때문일 수 있다. 또한, 옥트리 노드들의 고정된 크기는 방문해야 할 브랜치를 미리 계산하는 것을 용이하게 할 수 있다.12 하지만 이론적인 최악 시간 복잡도 측면에서는 3차원 데이터의 반경 탐색에서 k-d 트리가 O(N^{2/3})를 가지는 반면, 옥트리는 O(N)을 보장할 수 있어, 이론적으로는 k-d 트리가 우세하다는 상반된 분석도 존재한다.12 실제 성능은 데이터의 분포와 구현 방식에 따라 달라질 수 있다.
• 트리 구조 및 메모리 접근 패턴: k-d 트리는 이진 트리(binary tree)이므로, 각 노드가 8개의 자식을 갖는 옥트리에 비해 동일한 수의 데이터를 저장할 때 트리의 깊이가 더 깊어지는 경향이 있다. 더 깊은 트리는 탐색 시 더 많은 재귀 호출이나 스택 사용을 유발할 수 있다. 반면, 옥트리는 상대적으로 얕고 넓은 구조를 가지며, 8개의 자식 노드를 메모리 상에 연속적으로 배치하여 캐시 효율성(cache-friendliness)을 높이기에 더 유리한 구조를 가진다. 근접 이웃 탐색 시 부모-자식-형제 노드를 오가는 탐색이 빈번할 때, 이러한 캐시 친화적 접근은 상당한 성능 향상을 가져올 수 있다.12

이처럼 k-d 트리와 옥트리 간의 비교는 공간 분할 자료구조 설계에 있어 근본적인 설계 철학의 차이, 즉 데이터 종속적 분할과 공간 주도적 분할이라는 이분법을 명확히 보여준다. k-d 트리는 데이터의 기하학적 구조에 적응하여 분할을 최적화하는 반면, 옥트리는 데이터와 무관하게 공간 자체의 구조를 기반으로 분할한다. 이 차이점은 이후에 등장하는 복셀 기반 구조들(SVO, VDB 등)이 옥트리의 공간 주도적 특성을 계승하고, 포인트 클라우드 처리 구조들이 k-d 트리의 데이터 종속적 특성을 유지하는 경향으로 이어지는 중요한 맥락을 형성한다. 이 근본적인 분기를 이해하는 것이 전체 공간 분할 자료구조의 지형도를 파악하는 첫걸음이다.

3. 희소성 및 압축에 최적화된 고급 복셀 구조

기초적인 옥트리 구조는 공간을 효율적으로 표현하는 첫걸음이었지만, 컴퓨터 그래픽스와 시각 효과(VFX) 분야의 요구사항은 이를 훨씬 뛰어넘었다. 수십억, 수백억 개의 복셀로 이루어진 초고해상도 장면을 다루기 위해서는 단순한 공간 분할을 넘어, 데이터 자체의 희소성(sparsity)과 반복성(redundancy)을 적극적으로 활용하는 고도의 압축 기술이 필수적이었다. 본 장에서는 이러한 도전에 대응하기 위해 옥트리에서 진화한 세 가지 핵심적인 고급 복셀 구조, 즉 SVO, SVDAG, 그리고 VDB를 탐구한다. 이들의 발전 과정은 메모리 효율성을 향한 끊임없는 추구의 역사를 보여준다.

3.1 희소 복셀 옥트리 (Sparse Voxel Octree, SVO)

전통적인 밀집 복셀 그리드(dense voxel grid)는 3차원 공간을 균일한 격자로 표현하는 가장 간단한 방식이지만, 치명적인 확장성 문제를 안고 있다. 해상도가 한 축으로 N배 증가하면 필요한 메모리 양은 N3배로 폭발적으로 증가한다.24 예를 들어, 1cm 해상도로 100m x 100m x 100m 공간을 표현하려면 수 테라바이트의 메모리가 필요하다.25 이는 현실적으로 불가능하다.

3.1.1 개념 및 동기

**희소 복셀 옥트리(Sparse Voxel Octree, SVO)**는 이러한 문제를 해결하기 위해 등장했다. SVO의 핵심 아이디어는 대부분의 3차원 장면에서 실제 데이터가 차지하는 공간은 극히 일부이며, 나머지 대부분은 비어있다는 관찰에서 출발한다.26 SVO는 이 ’희소성’을 활용하여, 데이터가 존재하는(non-empty) 영역만을 옥트리 구조를 사용해 계층적으로 표현하고, 비어있는(empty) 노드에 대해서는 저장 공간을 할당하지 않는다.16

이 방식을 통해 메모리 사용량을 장면의 전체 부피가 아닌, 실제 콘텐츠의 표면적이나 부피에 비례하도록 크게 줄일 수 있다. 동시에, 계층 구조는 탐색 시 광선(ray) 등이 비어있는 거대한 공간을 단 한 번의 연산으로 건너뛸 수 있게(skip) 하여, 렌더링과 같은 질의 연산의 속도를 극적으로 향상시킨다.26

3.1.2 구조 및 메모리 레이아웃

SVO는 본질적으로 옥트리이지만, 그 구현은 성능 최적화를 위해 특별히 설계된다. 포인터 기반의 전통적인 트리 구조는 각 노드가 8개의 자식 포인터를 가지므로 메모리 오버헤드가 크고, 포인터 역참조(pointer dereferencing)로 인한 캐시 미스(cache miss)가 잦아 성능 저하의 원인이 될 수 있다.

이 문제를 해결하기 위해, 현대적인 SVO 구현에서는 트리 노드들을 포인터 대신 선형 배열(linear array)에 저장하는 방식을 선호한다. 이때 노드 간의 부모-자식 관계와 공간적 위치를 효율적으로 인코딩하기 위해 모튼 코드(Morton Code), 또는 Z-order 커브가 널리 사용된다.27 모튼 코드는 3차원 좌표 (x, y, z)의 이진 비트들을 서로 번갈아 끼워 넣어(interleaving) 하나의 1차원 정수 값으로 매핑하는 기법이다. 예를 들어, 2차원 좌표 (x, y) = (x_1x_0, y_1y_0)는 모튼 코드 y_1x_1y_0x_0로 인코딩된다.27 이 인코딩 방식은 공간적으로 가까운 점들이 1차원 코드 상에서도 가까운 값을 갖도록 하는 **공간적 지역성(spatial locality)**을 보존하는 중요한 특성을 가진다. 모튼 코드로 정렬된 선형 배열은 부모-자식-형제 노드 간의 이동을 간단한 비트 연산으로 수행할 수 있게 하여, 트리 순회를 매우 빠르고 캐시 친화적으로 만든다.28

3.1.3 주요 응용 분야

SVO의 희소성과 가속 구조로서의 특성은 다음과 같은 분야에서 강력한 성능을 발휘한다.

• 실시간 렌더링 (Real-time Rendering): SVO는 레이캐스팅(Raycasting)이나 레이트레이싱(Ray Tracing) 기법의 핵심 가속 구조로 사용된다.26 렌더링을 위해 발사된 광선이 SVO를 순회할 때, 비어있는 큰 노드를 만나면 광선이 해당 노드를 완전히 벗어날 때까지의 거리를 계산하여 한 번에 전진할 수 있다. 이를 ‘콘 트레이싱(cone tracing)’ 또는 ’빈 공간 건너뛰기(empty space skipping)’라고 하며, 렌더링에 필요한 샘플링 횟수를 극적으로 줄여 실시간 성능을 가능하게 한다.
• 3D 경로 탐색 (3D Pathfinding): 게임 AI나 로봇 공학에서 공중을 비행하는 에이전트의 경로를 계획하는 것은 복잡한 문제이다. 거대한 3D 공간을 균일 격자(regular grid)로 표현하는 것은 SVO가 해결하고자 했던 메모리 문제를 그대로 안고 있다.27 SVO는 이러한 3D 공간을 계층적으로 표현하여, 장애물이 없는 넓은 공간은 큰 노드로, 복잡한 지형은 작은 노드들로 나누어 효율적인 탐색 공간을 제공한다. A*와 같은 탐색 알고리즘을 SVO 상에서 수행하여 자연스러운 비행 경로를 효과적으로 찾아낼 수 있다.27

3.2 희소 복셀 방향성 비순환 그래프 (Sparse Voxel Directed Acyclic Graph, SVDAG)

SVO가 ’비어있는 공간’을 압축하는 데 초점을 맞췄다면, **희소 복셀 방향성 비순환 그래프(Sparse Voxel Directed Acyclic Graph, SVDAG)**는 여기서 한 걸음 더 나아가 ’반복되는 공간’을 압축하는 혁신적인 아이디어를 제시한다.

3.2.1 핵심 혁신

SVDAG의 핵심 철학은 많은 3차원 씬, 특히 인공적인 환경(예: 건물, 도시)이나 절차적으로 생성된 자연 환경(예: 숲, 지형)에는 동일한 기하학적 구조가 반복적으로 나타난다는 관찰에 기반한다.31 예를 들어, 한 건물에는 수많은 동일한 모양의 창문이 있고, 숲에는 비슷한 모양의 나무들이 반복된다.

SVO에서는 이러한 동일한 구조들이 공간적으로 다른 위치에 있다는 이유만으로 각각 별도의 서브트리로 저장되어 메모리 중복을 유발한다. SVDAG는 이 중복을 제거한다. 구조적으로 동일한 모든 서브트리(또는 노드)를 식별하여 메모리에는 단 하나의 유일한 인스턴스(unique instance)만 저장한다. 그리고 원래 이 서브트리들을 자식으로 가졌던 모든 부모 노드들은 이제 이 공유된 단일 인스턴스를 가리키는 포인터를 갖게 된다.32 이 포인터 공유(pointer sharing)로 인해, 자료구조는 더 이상 분기 후 합쳐지지 않는 ’트리’가 아니라, 여러 경로가 하나의 노드로 합쳐질 수 있는 **방향성 비순환 그래프(Directed Acyclic Graph, DAG)**의 형태를 띠게 된다.16

3.2.2 메커니즘

SVDAG를 구축하는 과정은 일반적으로 SVO를 먼저 구축한 후, 후처리 단계를 통해 이루어진다. 트리의 리프 노드부터 상향식(bottom-up)으로 순회하면서 각 노드의 구조적 정보를 해싱(hashing)하여 고유한 시그니처(signature)를 생성한다. 동일한 시그니처를 가진 노드들은 동일한 구조로 간주되어, 이전에 나타난 유일한 인스턴스를 가리키도록 포인터가 재지정되고 중복된 노드는 제거된다(de-duplication).33 이 과정을 통해 SVO 대비 수십 배에서 심지어 수백 배에 달하는 극적인 메모리 압축률을 달성할 수 있다.32 더 나아가, 거울 대칭(mirror symmetry)과 같은 변환(transformation)에 대해서도 동일한 것으로 간주하여 압축률을 더욱 높이는 연구도 진행되었다.16

3.2.3 성능 트레이드오프

SVDAG의 극단적인 압축률은 상당한 대가를 치른다.

• 장점: 기하학적 반복성이 높은 씬(예: 건축 모델, 도시 데이터)에서 타의 추종을 불허하는 메모리 효율성을 제공한다.31 이는 대규모 정적 씬을 저장하고 전송하는 데 매우 유리하다.
• 단점:

1. 탐색 성능 저하: 압축의 대가로 탐색 및 렌더링 성능이 저하될 수 있다. 레이 트레이싱 시, SVO에서는 광선이 트리를 따라 내려가기만 하면 되지만, SVDAG에서는 공유된 서브트리로 인해 탐색 경로가 복잡해지고, 각 노드의 실제 월드 공간 위치를 계산하기 위한 추가적인 변환 정보 관리가 필요하다. 이로 인해 SVO보다 렌더링 속도가 느려지는 경향이 있다.33
2. 동적 업데이트의 어려움: SVDAG의 가장 큰 약점은 동적 업데이트이다. 공유된 노드 하나를 수정하면, 그 노드를 참조하는 모든 상위 경로에 영향을 미친다. 이는 연쇄적인 ’복사 후 수정(copy-on-write)’을 유발하여 구조 전체를 재구성해야 할 수도 있다. 이 때문에 SVDAG는 본질적으로 정적인 데이터에 적합하다. 이 문제를 해결하기 위해 HashDAG와 같은 구조가 제안되었는데, 이는 해시 맵을 사용하여 동적 편집을 가능하게 하지만, 해시 테이블 유지를 위한 추가적인 메모리 오버헤드와 복잡성을 감수해야 한다.34

3.2.4 주요 응용 분야

SVDAG는 건축 시각화, 디지털 도시 모델, 절차적으로 생성된 게임 월드와 같이 반복적인 구조가 많고, 데이터가 거의 변하지 않는 대규모 정적 씬의 저장, 전송, 그리고 오프라인 렌더링에 매우 효과적인 솔루션이다.

3.3 VDB (Volumetric Dynamic B+Tree)

SVO와 SVDAG가 주로 정적인 씬의 메모리 효율성에 집중한 반면, VDB는 영화 산업의 특수한 요구사항, 즉 거대하고, 희소하며, 동적으로 끊임없이 변화하는 볼륨 데이터를 효율적으로 처리하기 위해 탄생했다.

3.3.1 구조 철학

VDB는 DreamWorks Animation에서 개발한 오픈 소스 라이브러리인 OpenVDB의 핵심 자료구조이다.35 그 이름(Volumetric, Dynamic, B-tree)이 암시하듯, VDB는 볼륨 데이터를 다루며, 동적 환경에 강하고, 데이터베이스 인덱싱에 널리 쓰이는 B+트리의 특성을 차용한 독특한 구조를 가진다.37 VDB의 설계 철학은 시뮬레이션 과정에서 매 프레임마다 형태가 변하는 연기, 불, 물, 구름과 같은 효과를 저장하고 조작하는 데 최적화되어 있다.

3.3.2 핵심 특징

VDB는 기존 옥트리 기반 구조들과는 차별화되는 여러 독창적인 특징을 가진다.

• 넓고 얕은 B+트리 유사 구조 (Wide and Shallow B+-tree like Structure): VDB 트리는 전통적인 옥트리처럼 깊지 않다. 대신, 매우 넓고 얕은(wide and shallow) 구조를 채택한다. 예를 들어, OpenVDB의 기본 5,4,3-레벨 구성에서, 가장 아래 레벨인 리프 노드(LeafNode, 3-노드)는 8×8×8=512개의 복셀 데이터를 직접 저장한다. 그 상위의 내부 노드(InternalNode, 4-노드)는 16×16×16=4096개의 자식 노드(리프 노드 또는 타일 값)에 대한 포인터나 값을 담는 테이블을 가진다. 최상위 내부 노드(5-노드)는 32×32×32=32768개의 4-노드에 대한 포인터를 가진다.37 이러한 구조는 임의의 복셀에 접근할 때 거쳐야 하는 노드의 수를 3~4개 수준으로 최소화하여, 임의 접근(random access) 성능을 극대화한다.38
• 효율적인 희소 표현: VDB는 여러 메커니즘을 통해 희소 데이터를 효율적으로 표현한다.

1. 배경 값 (Background Value): 그리드 전체에 대한 기본값을 정의한다. 어떤 위치에 접근했을 때 해당 위치에 명시적인 데이터가 없으면 이 배경 값이 반환된다. 이를 통해 사실상 무한한 빈 공간을 O(1)의 메모리로 표현할 수 있다.40
2. 타일 값 (Tile Value): 특정 내부 노드나 리프 노드 전체가 단일한 값으로 채워져 있을 경우, 개별 복셀 값을 저장하는 대신 이 ‘타일 값’ 하나만 저장한다. 이는 균일한 값으로 채워진 넓은 영역을 매우 효율적으로 압축한다.40
3. 활성/비활성 상태 (Active/Inactive State): VDB는 각 복셀의 ’값’뿐만 아니라 ’활성 상태’도 관리한다. 예를 들어, 레벨셋(level set) 표현 시, 표면 근처의 좁은 밴드(narrow band)에 있는 복셀들만 ’활성’으로 표시하고, 내부와 외부의 복셀들은 ’비활성’으로 둔다. 이를 통해 연산이 필요한 영역(활성 복셀)에만 집중할 수 있다.40

• 빠른 동적 업데이트: VDB의 가장 강력한 장점 중 하나는 동적 데이터 처리에 있다. B+트리의 특성 덕분에, 새로운 데이터를 삽입하거나 기존 데이터를 삭제/수정하는 연산이 트리의 전반적인 재구성 없이 국소적인 노드 수정만으로 이루어진다. 이로 인해 데이터의 삽입, 삭제, 검색이 평균적으로 O(1)에 가까운 매우 빠른 시간 복잡도를 가진다 (정확히는 트리의 높이에 비례하는 O(\log_B N)이며, 여기서 B는 노드의 팬아웃으로 매우 크므로 사실상 상수 시간에 가깝다).38 이는 매 타임 스텝마다 데이터가 전역적으로 변하는 유체 시뮬레이션과 같은 응용에 매우 적합하다.
• 유연한 좌표계 변환 (Flexible Coordinate System Transform): 각 VDB 그리드는 자체적인 변환(Transform) 객체를 가질 수 있다. 이 변환 객체는 복셀의 인덱스 공간 좌표 (i, j, k)를 실제 물리적인 월드 공간 좌표 (x, y, z)로 매핑하는 역할을 한다. 이 변환에는 스케일(voxel size), 회전, 이동 등이 포함될 수 있어, 그리드를 월드 공간 내에서 자유롭게 배치하고 변형할 수 있는 높은 유연성을 제공한다.40

3.3.3 주요 응용 분야

VDB는 개발 초기부터 시각 효과(VFX) 산업의 요구에 맞춰 설계되었으며, 현재 이 분야의 사실상 표준(de facto standard)으로 자리 잡았다.35 유체 시뮬레이션(물, 연기, 불), 구름 및 대기 효과, 폭발, 지형 표현 등 희소하고 동적인 특성을 가진 다양한 볼륨 데이터를 저장, 처리, 렌더링하는 데 광범위하게 사용된다.38 최근에는 NanoVDB를 통해 GPU 가속을 지원하고, 로보틱스 분야의 맵 표현 등 다른 영역으로도 활용이 확대되고 있다.36

이 세 가지 고급 복셀 구조의 진화는 압축 전략의 발전을 명확히 보여준다. 옥트리와 SVO는 ’비어있는 공간의 제거’라는 첫 번째 논리적 도약을 이루었다. SVDAG는 여기서 더 나아가 ’반복되는 구조의 제거’라는 두 번째, 더 정교한 도약을 이루었다. 반면, VDB는 이들과는 다른 축, 즉 ’동적 데이터의 효율적 관리’에 초점을 맞춰 발전했다. SVO가 희소성을 압축하고, SVDAG가 중복성을 압축하며, VDB가 역동성을 효율적으로 다루는 것처럼, 각각은 대규모 공간 데이터가 제기하는 서로 다른 종류의 문제에 대한 특화된 해결책이라 할 수 있다.

4. 실시간 동적 응용을 위한 고성능 구조

컴퓨터 그래픽스가 주로 정적이고 거대한 세계를 효율적으로 ’저장’하고 ’렌더링’하는 문제에 집중했다면, 로보틱스, 자율 주행, 실시간 시뮬레이션과 같은 분야는 다른 종류의 도전에 직면한다. 이 분야들의 핵심 과제는 정적인 세계를 표현하는 것이 아니라, 센서로부터 끊임없이 쏟아져 들어오는 데이터를 최소한의 지연 시간(latency)으로 ’처리’하고, 그에 맞춰 빠르게 상태를 ’업데이트’하는 것이다. 본 장에서는 이러한 실시간 동적 환경의 요구사항을 충족시키기 위해 발전한 고성능 자료구조들을 탐구한다. 이들의 진화는 복잡한 계층 구조를 유지하기보다는, 극단적인 업데이트 속도를 위한 빠른 인덱싱 기법으로 나아가는 경향을 보인다.

4.1 동적 균형 옥트리 (Dynamic Balanced Octree)

많은 과학 및 공학 시뮬레이션, 특히 유한 요소 해석(Finite Element Method, FEM)이나 전산 유체 역학(Computational Fluid Dynamics, CFD)에서는 계산에 사용되는 메시(mesh)의 품질이 해석의 정확성과 수치적 안정성에 결정적인 영향을 미친다. 옥트리를 메시 생성에 사용할 때, 인접한 셀(octant) 간의 크기 차이가 너무 급격하게 변하면 수치 오류나 불안정성을 야기할 수 있다.

4.1.1 핵심 제약: 2:1 균형

이러한 문제를 방지하기 위해 2:1 균형 제약(2:1 balance constraint) 또는 ’연속성 조건(continuity condition)’이 도입되었다.43 이 제약은 공간적으로 인접한(면 또는 모서리를 공유하는) 두 개의 리프 노드의 크기(즉, 레벨) 차이가 2배(즉, 1 레벨)를 초과해서는 안 된다는 조건이다.43 예를 들어, 레벨 4의 셀 옆에 레벨 2의 셀이 직접 위치할 수 없으며, 그 사이에는 반드시 레벨 3의 셀이 존재해야 한다. 이를 통해 메시의 크기가 공간에 걸쳐 부드럽게 변하도록 보장하여, T-교차점(T-junction) 문제를 완화하고 고품질의 메시를 생성할 수 있다.44

4.1.2 균형 재정의 (Balance Refinement)

데이터의 추가(refinement)나 삭제(coarsening)로 인해 옥트리의 일부 영역에서 2:1 균형 제약이 깨질 수 있다. 이때, 제약을 다시 만족시키기 위해 옥트리를 수정하는 과정을 **균형 재정의(balance refinement)**라고 한다.43 예를 들어, 어떤 셀이 분할되어 그 자식 중 하나가 기존의 큰 이웃 셀과 2:1 제약을 위반하게 되면, 그 큰 이웃 셀 또한 강제로 분할되어야 한다. 이러한 분할은 또 다른 이웃과의 제약을 위반할 수 있으며, 이로 인해 수정 작업이 인접 노드로 연쇄적으로 전파되는 **파급 효과(ripple propagation)**가 발생할 수 있다.43 이 과정은 특히 병렬 환경에서 여러 프로세서에 걸쳐 데이터가 분산되어 있을 때 통신 오버헤드를 유발하는 복잡한 작업이 될 수 있다.44

4.1.3 선형 옥트리 (Linear Octree)

수십억 개 이상의 옥턴트를 사용하는 대규모 시뮬레이션에서는 전체 옥트리를 메인 메모리에 상주시키는 것이 불가능하다. 이러한 대용량 데이터셋에서 동적 균형을 효율적으로 관리하기 위해 선형 옥트리(linear octree) 표현법이 널리 사용된다.43

선형 옥트리는 포인터로 노드들을 연결하는 전통적인 트리 구조 대신, 트리의 리프 노드들만을 리스트 형태로 저장한다. 각 리프 노드는 모튼 코드와 같은 **위치 코드(locational code)**를 통해 고유하게 식별된다. 이 위치 코드는 노드의 공간적 위치와 크기(레벨) 정보를 모두 인코딩한다.43 모든 리프 노드들의 위치 코드를 정렬하여 배열이나 리스트에 저장하면, 이 데이터 자체가 옥트리의 전체 구조를 암시적으로 표현하게 된다. 이 정렬된 리스트는 일반적으로 디스크 상에 B-트리(B-tree)와 같은 인덱스 구조를 사용하여 효율적으로 관리된다.43

이러한 접근법은 자료구조의 크기가 메모리가 아닌 디스크 용량에 의해 제한되도록 하여, 메모리 용량을 훨씬 초과하는 거대한 옥트리 데이터셋을 다룰 수 있게 해준다. 동적 균형 재정의 알고리즘은 이 선형 옥트리 위에서 디스크 기반의 정렬 및 병합 연산을 통해 수행된다.43

4.2 해시 기반 복셀 구조 (iVox & iVox-PHC)

로보틱스, 특히 LiDAR-관성 주행 거리 측정(Lidar-Inertial Odometry, LIO) 분야는 또 다른 차원의 실시간성을 요구한다. 여기서는 매초 수십 번씩 수만 개의 점으로 구성된 LiDAR 스캔 데이터가 들어오며, 시스템은 이 데이터를 즉시 처리하여 로봇의 위치를 추정하고 맵을 업데이트해야 한다. 이러한 환경에서는 i-kd-tree조차도 트리 재균형에 드는 비용이 부담스러울 수 있다.

4.2.1 핵심 개념

**iVox(incremental Voxel)**는 이러한 초고속 증분 업데이트 요구사항을 충족시키기 위해 설계된 자료구조이다. iVox의 핵심적인 발상은 복잡한 트리 구조를 완전히 버리고, 점들을 담고 있는 희소한 복셀들을 **해시 맵(hash map, C++의 std::unordered_map)**을 사용하여 직접 인덱싱하는 것이다.13 점의 공간 좌표를 해시 함수에 입력하여 해시 키를 계산하고, 이 키를 사용해 해당 복셀에 대한 데이터에 O(1)의 평균 시간 복잡도로 접근한다.

4.2.2 메커니즘

• 초고속 업데이트: 해시 맵의 삽입 및 삭제 연산은 평균적으로 상수 시간(O(1))에 완료된다. 따라서 새로운 LiDAR 스캔으로부터 들어온 점들을 맵에 추가하거나, 오래된 점들을 제거하는 작업이 트리 기반 구조에 비해 압도적으로 빠르다. iVox는 매 스캔마다 트리를 재구성하거나 재균형해야 하는 부담에서 완전히 자유롭다.13
• 효율적인 맵 관리: 전역 맵(global map) 전체를 메모리에 유지하는 대신, iVox는 로봇의 현재 위치 주변의 로컬 맵(local map)만을 유지하는 전략을 사용한다. 이는 LRU(Least Recently Used) 캐시 전략과 유사하게, 오래된 복셀이나 로봇의 시야에서 벗어난 복셀을 주기적으로 제거하여 메모리 사용량을 일정하게 유지하고, 탐색 범위를 제한하여 성능을 높인다.13

4.2.3 두 가지 변형

iVox는 복셀 내부에 점들을 저장하는 방식에 따라 두 가지 변형을 가진다.13

1. linear iVox: 각 복셀 내부에 포함된 점들을 단순한 벡터(vector)나 연결 리스트(linked list)와 같은 선형 구조로 저장한다. 이 경우, 특정 복셀 내에서 k-NN 탐색을 수행하려면 해당 복셀 안의 모든 점들과의 거리를 계산해야 하므로, 복셀 내 점의 수를 n이라 할 때 O(n)의 시간 복잡도를 가진다. 이 방식은 복셀 당 점의 수가 적을 때 간단하고 효율적이다.
2. iVox-PHC (Pseudo Hilbert Curve iVox): 복셀 내의 점 밀도가 높을 때 linear iVox의 k-NN 탐색 성능을 개선하기 위해 제안되었다. 이 변형은 각 복셀 내부 공간을 다시 **유사 힐버트 곡선(Pseudo Hilbert Curve, PHC)**이라는 공간 채움 곡선으로 구조화한다. 점들은 PHC 인덱스에 따라 정렬되어 저장된다. 이를 통해 복셀 내 k-NN 탐색을 1차원 정렬 배열에서의 탐색과 유사하게 수행할 수 있어, 시간 복잡도를 O(logn) 또는 PHC의 차수(order) κ에 비례하는 O(\kappa)로 크게 줄일 수 있다. 복셀 당 점의 수가 많을 때 더 나은 계산 효율성을 보인다.

4.2.4 성능

실험 결과에 따르면, iVox는 LIO 응용에서 기존의 트리 기반 구조들을 월등히 능가하는 성능을 보인다. 한 연구에서는 iVox가 i-kd-tree에 비해 트리 구축에서 64%, 점 삽입에서 66%, k-NN 탐색에서 30%, 반경 탐색에서 56%의 런타임 감소를 보였다고 보고했다.14 이는 iVox의 해시 기반 접근법이 실시간 동적 환경에 얼마나 효과적인지를 명확히 보여준다.

4.3 로봇 중심 복셀 맵 (RC-Vox)

iVox가 해시 맵을 통해 트리 구조를 탈피했다면, **RC-Vox(Robocentric Voxel map)**는 여기서 한 걸음 더 나아가 해시 맵조차도 제거하고 원시적인 3D 배열을 사용하여 극단적인 속도 최적화를 추구한다.

4.3.1 구조 혁신

RC-Vox는 LIO 시스템의 효율성을 극한까지 끌어올리기 위해 제안된 구조로, 그 핵심은 로봇을 중심으로 하는 고정된 크기의 2계층 3D 배열을 사용하는 것이다.49

4.3.2 메커니즘

• 2계층 배열 구조: RC-Vox는 두 개의 배열 계층으로 구성된다.

1. 최상위 레벨 배열 (Top-Level Array, TLA): 상대적으로 낮은 해상도(예: 미터 단위)를 가진 3D 배열이다.

2. 하위 레벨 배열 (Bottom-Level Array, BLA): TLA의 각 셀(grid)은 필요에 따라 내부에 더 높은 해상도의 BLA를 생성하여 실제 복셀들을 저장한다.

이 2계층 구조는 메모리 사용을 관리하면서도 빠른 접근을 가능하게 한다.49

• 로봇 중심 및 모듈러 연산: 이 배열은 가상의 무한한 공간을 표현하는 것이 아니라, 항상 현재 로봇의 위치를 중심으로 하는 고정된 크기의 로컬 맵을 나타낸다. 로봇이 이동하여 로컬 맵의 범위가 이 고정된 TLA 배열의 경계를 벗어나게 되면, 모듈러(modulo) 연산을 사용하여 벗어난 그리드를 배열의 반대편으로 다시 매핑하고 그 내용을 초기화(reset)한다.49 이는 마치 팩맨 게임의 맵처럼, 한쪽 끝으로 나가면 반대쪽 끝으로 나타나는 효과를 내며, 고정된 크기의 배열로 지속적으로 움직이는 로컬 맵을 효율적으로 관리할 수 있게 한다.

• k-NN 탐색의 혁신적 최적화: RC-Vox의 가장 독창적인 부분은 k-NN 탐색을 최적화하는 방식에 있다. 전통적인 방식에서는 질의 시점(query time)에 주변 공간을 탐색하여 이웃 점들을 찾는다. 하지만 RC-Vox는 이 작업을 **매핑 시점(mapping time)**으로 옮긴다. 즉, 새로운 LiDAR 점이 시스템에 등록되어 특정 복셀에 추가될 때, 그 점을 해당 복셀에만 저장하는 것이 아니라, 그 주변의 인접한 26개 복셀에도 미리 복사하여 기록해 둔다.49 이 작업은 매핑 시점에 약간의 추가 비용을 발생시키지만, 매핑은 증분적으로 소수의 점에 대해서만 일어나므로 전체적인 부담은 미미하다.

이러한 사전 작업 덕분에, 실제 k-NN 질의가 필요한 시점에는 매우 빠른 속도를 자랑한다. 질의점의 이웃을 찾기 위해 주변 복셀들을 탐색할 필요 없이, 단순히 질의점이 속한 단 하나의 복셀을 조회하기만 하면 된다. 그 복셀에는 이미 필요한 모든 이웃 점들이 기록되어 있기 때문이다. 이 전략은 k-NN 탐색 과정을 사실상 O(k)의 간단한 거리 계산 및 정렬 문제로 바꾸어 버린다.

4.3.3 성능

원시 배열의 직접 접근(O(1))과 혁신적인 k-NN 탐색 전략 덕분에, RC-Vox는 현존하는 LIO 시스템 중 가장 빠른 성능을 보인다. 한 연구에서는 RC-Vox의 단일 스레드 버전이 iVox를 사용하는 Faster-LIO의 병렬 가속 버전보다도 더 빠르다고 보고했다.49 이는 특히 로봇이 격렬하게 움직이는 공격적인 모션 시나리오에서도 안정적인 트래킹을 가능하게 하는 핵심 요인이다.

이러한 고성능 동적 구조들의 발전 과정은 실시간 응용을 위한 최적화 철학의 변화를 명확히 보여준다. 동적 균형 옥트리가 여전히 ’트리’라는 복잡한 계층 구조를 유지하려 했다면, iVox는 “정말 트리가 필요한가? 빠른 조회가 핵심이 아닌가?“라는 질문을 던지며 해시 맵이라는 빠른 ’인덱싱’으로 전환했다. RC-Vox는 여기서 더 나아가 “해시 맵보다 더 빠른 것은 없나?“라는 질문에 ’원시 배열’이라는 답을 내놓았다. 이 과정은 풍부한 계층적 정보를 포기하는 대신, 오직 업데이트와 질의 속도를 극대화하기 위한 무자비한 최적화의 역사라 할 수 있다. LIO와 같은 응용에서는 전체 씬의 구조를 아는 것보다, ‘지금 당장’ 내 주변의 가장 가까운 점들을 찾는 것이 훨씬 중요하기 때문이다.

5. 종합 비교 분석 및 결론

지금까지 개별적으로 분석한 10가지 공간 분할 자료구조의 특성을 종합하여, 이들의 관계와 성능 트레이드오프를 다각적으로 조명하고, 실제 응용에 적합한 자료구조를 선택하기 위한 실용적인 가이드라인을 제시한다.

5.1 핵심 특성 및 복잡도 비교

본 안내서에서 다룬 10가지 자료구조의 핵심적인 특징, 기반 기술, 성능 복잡도, 그리고 주요 응용 분야를 요약하여 비교하면 다음과 같다. 이 표는 각 기술의 장단점을 한눈에 파악하고, 특정 요구사항에 맞는 기술을 필터링하는 데 유용한 기준을 제공한다.

표 1: 공간 분할 자료구조 종합 비교표

5.2 성능 축에 따른 그룹화 및 심층 분석

자료구조들을 특정 성능 축을 기준으로 그룹화하면, 이들의 진화적 맥락과 설계 철학을 더 깊이 이해할 수 있다.

5.2.1 메모리 압축 축: Octree –>> SVO –>> VDB –>> SVDAG

이 그룹의 자료구조들은 주로 정적이거나 서서히 변하는 대규모 씬을 효율적으로 ’저장’하는 문제에 집중한다. 이들의 진화는 압축 전략의 발전으로 요약될 수 있다.

• 1단계 (빈 공간 제거): 전통적인 옥트리는 데이터가 없는 노드를 분할하지 않음으로써 기본적인 희소성을 표현한다. SVO는 이 개념을 극대화하여, 데이터가 있는 복셀만을 명시적으로 저장하고 광대한 빈 공간을 효율적으로 건너뛰는 메커니즘을 제공한다.26 이는 메모리 사용량을 전체 공간의 부피가 아닌, 콘텐츠의 표면적에 비례하도록 만드는 첫 번째 중요한 도약이다.
• 2단계 (희소 동적 데이터 최적화): VDB는 SVO와 유사하게 희소성을 다루지만(배경/타일 값), B+트리 기반의 넓고 얕은 구조를 통해 동적 데이터의 삽입/삭제 성능을 극대화했다.38 이는 정적인 압축률보다는 시뮬레이션과 같은 동적 환경에서의 메모리 관리 및 접근 속도에 초점을 맞춘 결과이다.
• 3단계 (기하학적 중복 제거): SVDAG는 압축의 정점을 보여준다. SVO가 빈 공간을 제거했다면, SVDAG는 한발 더 나아가 데이터가 존재하는 영역 내에서도 반복적으로 나타나는 기하학적 패턴을 찾아내 중복을 제거한다.32 동일한 서브트리를 단 한 번만 저장하고 공유하는 DAG 구조를 통해, SVO조차도 감당하기 힘든 초고해상도 정적 씬을 실용적인 메모리 용량으로 저장할 수 있게 되었다.

이 그룹 내에는 명확한 트레이드오프가 존재한다. 압축률이 높아질수록(Octree –>> SVO –>> SVDAG), 일반적으로 구조가 복잡해지고 동적 업데이트가 어려워지며, 때로는 탐색 성능(특히 레이 트레이싱)이 저하될 수 있다.33 VDB는 이 축에서 약간 벗어나, 높은 압축률보다는 동적 성능과 유연성에 우선순위를 둔 독자적인 위치를 차지한다.

5.2.2 동적 업데이트 속도 축: kd-tree –>> i-kd-tree –>> 동적 균형 Octree –>> VDB –>> iVox –>> RC-Vox

이 그룹의 자료구조들은 데이터가 실시간으로 빠르게 변하는 동적 환경에서의 ’처리 속도’를 최적화하는 데 집중한다. 이들의 진화는 복잡한 트리 구조를 점차 버리고 단순하고 빠른 인덱싱 방식으로 나아가는 과정으로 볼 수 있다.

• 전통적 트리의 동적화: 정적 kd-tree나 Octree는 동적 업데이트에 취약하다. 이를 개선하기 위해 i-kd-tree는 부분 재구축 기법을 14,

동적 균형 Octree는 2:1 제약을 유지하기 위한 파급 효과 처리 메커니즘을 도입했다.43 이들은 여전히 ’트리’라는 계층 구조의 틀 안에서 동적 성능을 개선하려는 시도이다.

• 새로운 패러다임 (B+트리): VDB는 B+트리의 특성을 차용하여, 트리 구조를 유지하면서도 평균 O(1)에 가까운 빠른 삽입/삭제 성능을 달성했다. 이는 전통적인 이진 트리나 옥트리와는 다른 접근법으로, 동적 성능과 구조적 유연성 사이의 뛰어난 균형을 제공한다.38

• 트리 구조의 탈피 (해시 맵): iVox는 LIO와 같은 극단적인 실시간 요구사항 앞에서 트리 구조 자체가 오버헤드라는 결론에 도달했다. 복잡한 계층적 관계를 버리고, 공간 좌표를 직접 해시 키로 변환하여 해시 맵에 접근하는 방식을 채택했다.13 이를 통해 트리 재균형과 관련된 모든 비용을 제거하고, 순수한

O(1) 평균 업데이트 성능을 달성했다.

• 구조의 극한적 단순화 (배열): RC-Vox는 iVox보다 한 걸음 더 나아가, 해시 맵의 잠재적인 충돌 및 오버헤드마저 제거하기 위해 원시 3D 배열을 사용한다.49 로봇 중심의 고정된 배열과 모듈러 연산을 결합하여 무한 공간을 시뮬레이션하고, k-NN 탐색 로직을 매핑 시점으로 이전하는 혁신을 통해 업데이트와 탐색 모두에서 극한의 속도를 추구한다.49

이 그룹 내의 트레이드오프는 업데이트 속도 vs. 구조적 정보의 풍부함으로 요약된다. RC-Vox로 갈수록 업데이트 속도는 빨라지지만, SVO나 VDB가 제공하는 전역적인 계층 구조나 다중 해상도 분석과 같은 풍부한 기능은 상실하게 된다.

5.3 최적의 자료구조 선택을 위한 가이드라인

어떤 자료구조가 ’최고’라고 단정할 수는 없다. 최적의 선택은 전적으로 응용 프로그램의 구체적인 요구사항에 달려있다. 다음은 적절한 자료구조를 선택하는 데 도움이 되는 의사결정 가이드라인이다.

1. 데이터의 특성은 무엇인가?

• 점 데이터 vs. 복셀 데이터: 데이터가 연속적인 좌표를 가진 점들의 집합인가, 아니면 공간을 채우는 복셀인가? 전자는 kd-tree 계열, 후자는 Octree 계열에서 출발하는 것이 자연스럽다.
• 정적 vs. 동적: 데이터가 한 번 구축된 후 거의 변하지 않는가, 아니면 실시간으로 계속 추가/삭제/수정되는가? 정적 데이터에는 SVO, SVDAG가, 동적 데이터에는 i-kd-tree, VDB, iVox, RC-Vox가 적합하다.
• 희소성 및 반복성: 씬이 대부분 비어있는가? (SVO, VDB) 기하학적 패턴이 많이 반복되는가? (SVDAG)

2. 주요 연산은 무엇인가?

• 읽기 vs. 쓰기: 데이터 질의(읽기)가 압도적으로 많은가, 아니면 업데이트(쓰기)가 빈번한가? 읽기 위주의 정적 씬 렌더링에는 SVDAG, 쓰기 위주의 실시간 매핑에는 RC-Vox가 극단에 위치한다.

• k-NN vs. 반경 탐색: k-NN 탐색이 주 목적이라면 kd-tree가 전통적으로 강점을 보이지만 12, LIO와 같이 특화된 k-NN 탐색에서는

iVox, RC-Vox가 월등하다. 일반적인 반경 탐색은 Octree가 좋은 성능을 보일 수 있다.12

3. 시스템 제약은 무엇인가?

• 메모리: 메모리 용량이 극도로 제한적인가? 그렇다면 SVDAG와 같은 고압축 구조가 유일한 대안일 수 있다.
• 실시간 응답성: 수 밀리초(ms) 단위의 지연 시간(latency)이 중요한가? 그렇다면 업데이트 오버헤드가 거의 없는 iVox나 RC-Vox를 고려해야 한다.
• 구현 복잡성: 개발 기간과 노력이 제한적인가? kd-tree나 기본적인 Octree는 상대적으로 구현이 간단하지만, VDB나 SVDAG는 매우 복잡한 라이브러리를 필요로 한다.

5.3.1 예시 시나리오 기반 추천

• 자율주행차 LiDAR 처리: 센서 데이터가 초당 10~20회씩 스트리밍되며, 매번 로컬 맵에 대해 k-NN 기반의 점 정합(registration)을 수행해야 한다. 극도로 낮은 업데이트 지연 시간과 빠른 k-NN 탐색이 필수적이다. 데이터는 로봇 주변의 로컬 맵에 한정된다.
• 추천: RC-Vox 또는 iVox. 이들은 LIO 응용을 위해 특별히 설계되었으며, 타의 추종을 불허하는 동적 업데이트 및 탐색 성능을 제공한다.
• 대규모 디지털 트윈 도시 모델 렌더링: 수백 제곱킬로미터에 달하는 도시를 상세하게 시각화해야 한다. 메모리 효율성이 가장 중요한 제약 조건이다. 씬은 대부분 정적이며, 건물, 가로등, 창문 등 반복적인 구조가 매우 많다.
• 추천: SVDAG. 기하학적 중복 제거를 통해 압도적인 메모리 압축률을 제공하여, 다른 구조로는 불가능한 규모의 씬을 다룰 수 있게 한다.
• 영화의 연기 및 폭발 시뮬레이션: 수억 개의 복셀로 구성된 유체 볼륨이 매 프레임마다 동적으로 변한다. 데이터는 희소하며(대부분 공기), 시뮬레이션 과정에서 임의의 위치에 대한 접근이 빈번하게 필요하다.
• 추천: VDB. 동적 토폴로지 변경에 매우 효율적이며, 희소 볼륨 데이터의 저장 및 조작을 위한 풍부한 도구 모음을 제공하는 산업 표준이다.
• 수백만 개 점 집합에서 통계 분석을 위한 k-NN 검색: 일반적인 다차원 점 데이터에 대한 오프라인 분석 작업. 데이터는 정적이며, k-NN 검색 성능이 중요하다.
• 추천: kd-tree. 구현이 용이하고 널리 알려져 있으며, 저차원 데이터에 대한 k-NN 검색에서 여전히 표준적이고 효율적인 선택이다.

5.4 결론

5.4.1 핵심 발전 동향 요약

본 안내서에서 분석한 공간 분할 자료구조의 역사는 범용적인 초기 구조인 kd-tree와 octree에서 출발하여, 특정 응용 분야의 극한 요구사항을 만족시키기 위한 두 가지 주요 방향으로 분화하고 심화되어 왔음을 명확히 보여준다.

1. 메모리 압축의 극대화 (그래픽스 분야): 대규모 씬을 표현하기 위한 메모리 한계를 극복하기 위해, Octree는 SVO로 발전하여 빈 공간을 효율적으로 압축했고, 이는 다시 SVDAG로 진화하여 기하학적 중복성까지 제거하는 수준에 이르렀다. VDB는 이 흐름 속에서 동적 특성을 강화한 독자적인 경로를 개척했다. 이 흐름의 핵심 동인은 저장 효율성이다.
2. 실시간 동적 성능의 극대화 (로보틱스 분야): 실시간 센서 데이터를 처리하기 위해, 동적 환경에 취약했던 kd-tree는 i-kd-tree로, Octree는 동적 균형 Octree로 발전했다. 그러나 진정한 돌파구는 트리 구조 자체를 버리는 데서 나왔다. iVox와 RC-Vox는 해시 맵과 원시 배열이라는 극도로 단순한 인덱싱 기법을 채택하여, 업데이트 지연 시간을 최소화했다. 이 흐름의 핵심 동인은 처리 속도이다.

5.4.2 핵심 트레이드오프 재확인

결론적으로, ‘최고의’ 공간 분할 자료구조는 존재하지 않으며, 모든 설계에는 근본적인 트레이드오프가 내재되어 있다. 본 안내서에서 분석한 모든 구조는 다음의 핵심적인 트레이드오프 관계 위에서 자신의 위치를 정의한다.

• 메모리 사용량 vs. 연산 복잡도: SVDAG처럼 압축률이 높을수록 구조가 복잡해지고 업데이트 및 특정 탐색 연산이 느려지는 경향이 있다.
• 탐색 성능 vs. 업데이트 성능: RC-Vox처럼 업데이트 성능을 극대화하면, 전역적인 계층 정보를 활용하는 복잡한 탐색 기능은 제한될 수 있다.
• 범용성 vs. 특정 응용 최적화: kd-tree와 Octree는 다양한 문제에 적용될 수 있는 범용성을 가지지만, VDB나 RC-Vox는 각각 VFX와 LIO라는 특정 도메인의 문제에 대해 압도적인 성능을 발휘하도록 고도로 특화되어 있다.

5.4.3 향후 전망

공간 분할 자료구조 분야는 계속해서 진화하고 있다. 향후 발전은 몇 가지 방향으로 예측될 수 있다. 첫째, GPU 아키텍처의 병렬 처리 능력을 최대한 활용하는 방향으로의 발전이 가속화될 것이다. OpenVDB의 NanoVDB는 VDB 구조를 GPU에 최적화하여 실시간 렌더링 및 시뮬레이션을 가능하게 한 좋은 예이다.36 둘째, 본 안내서에서 분석한 여러 구조의 장점을 결합한 하이브리드 자료구조에 대한 연구가 활발해질 것이다. 예를 들어, VDB의 동적 특성과 SVDAG의 압축률을 결합하려는 시도나, iVox의 빠른 업데이트와 kd-tree의 효율적인 탐색을 결합하려는 시도가 나타날 수 있다. 마지막으로, 최근 급부상하는 딥러닝 기반의 새로운 공간 표현 방식(예: NeRF, 3D Gaussian Splatting)이 전통적인 이산적 공간 분할 자료구조와 어떻게 상호작용하고 융합될 것인지가 중요한 연구 주제가 될 것이다.24 이러한 새로운 패러다임들은 기존 자료구조를 대체하기보다는, 특정 작업(예: 뷰 합성)에 대해 상호 보완적으로 사용되거나, 신경망 학습을 위한 기본 데이터 구조로 활용될 가능성이 높다. 결국, 미래의 공간 데이터 처리는 단일한 만능 해결책이 아닌, 문제의 특성에 따라 다양한 기술을 조합하여 사용하는 더욱 정교하고 다각적인 접근법을 요구하게 될 것이다.

6. 참고자료

1. Spatial Partition - Game Programming Patterns, accessed August 5, 2025, https://gameprogrammingpatterns.com/spatial-partition.html
2. Comparison of spatial partitioning data structures in … - DiVA portal, accessed August 5, 2025, https://www.diva-portal.org/smash/get/diva2:1595833/FULLTEXT01.pdf
3. Spatial Partitioning and Indexing - GITTA - Geographic Information Technology Training Alliance, accessed August 5, 2025, http://www.gitta.info/SpatPartitio/en/text/SpatPartitio.pdf
4. K-D Trees in Data Structures - Tutorialspoint, accessed August 5, 2025, https://www.tutorialspoint.com/data_structures_algorithms/k_d_trees.htm
5. k-d tree - Wikipedia, accessed August 5, 2025, https://en.wikipedia.org/wiki/K-d_tree
6. 15.4. KD Trees - CS3 Data Structures & Algorithms - OpenDSA, accessed August 5, 2025, https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/KDtree.html
7. KD-Tree Nearest Neighbor Data Structure - YouTube, accessed August 5, 2025, https://www.youtube.com/watch?v=Glp7THUpGow&pp=0gcJCfwAo7VqN5tD
8. What is a K-Dimensional Tree? - Medium, accessed August 5, 2025, https://medium.com/@katyayanivemula90/what-is-a-k-dimensional-tree-8265cc737d77
9. R*-Grove: Balanced Spatial Partitioning for Large-Scale Datasets - Frontiers, accessed August 5, 2025, https://www.frontiersin.org/journals/big-data/articles/10.3389/fdata.2020.00028/full
10. K-D Trees: A Deep Dive into Efficient Data Structures - Number Analytics, accessed August 5, 2025, https://www.numberanalytics.com/blog/k-d-trees-deep-dive
11. KD Trees in C++ - GeeksforGeeks, accessed August 5, 2025, https://www.geeksforgeeks.org/cpp/kd-trees-in-cpp/
12. kd-tree vs octree for 3d radius search - Stack Overflow, accessed August 5, 2025, https://stackoverflow.com/questions/17998103/kd-tree-vs-octree-for-3d-radius-search
13. (PDF) Faster-LIO: Lightweight Tightly Coupled Lidar-Inertial …, accessed August 5, 2025, https://www.researchgate.net/publication/359662313_Faster-LIO_Lightweight_Tightly_Coupled_Lidar-Inertial_Odometry_Using_Parallel_Sparse_Incremental_Voxels
14. A Fast, Lightweight, and Dynamic Octree for Proximity Search - arXiv, accessed August 5, 2025, https://arxiv.org/html/2309.08315v2
15. Implicit k-d tree - Wikipedia, accessed August 5, 2025, https://en.wikipedia.org/wiki/Implicit_k-d_tree
16. Transform-Aware Sparse Voxel Directed Acyclic Graphs - TU Delft …, accessed August 5, 2025, https://research.tudelft.nl/en/publications/transform-aware-sparse-voxel-directed-acyclic-graphs
17. Accelerated and Extended Building of Implicit kd-Trees for Volume Ray Tracing - CiteSeerX, accessed August 5, 2025, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=79d887badc13eaeb5279e9875a084999d4bb11aa
18. Wald’s [24] implicit kd-tree. | Download Scientific Diagram - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/figure/Walds-24-implicit-kd-tree_fig1_38015491
19. 4.2. How octree works - Castle Game Engine, accessed August 5, 2025, https://castle-engine.io/vrml_engine_doc/output/xsl/html/section.how_octree_works.html
20. Octrees: The Ultimate Spatial Data Structure - Number Analytics, accessed August 5, 2025, https://www.numberanalytics.com/blog/octrees-ultimate-spatial-data-structure
21. Mastering Octrees in Algorithm Design - Number Analytics, accessed August 5, 2025, https://www.numberanalytics.com/blog/ultimate-guide-to-octree-in-algorithm-design
22. Using Octrees and A* for Efficient Pathfinding - YouTube, accessed August 5, 2025, https://www.youtube.com/watch?v=gNmPmWR2vV4
23. Why specifically are k-d trees preferred in ray tracing and octrees in collision? - Reddit, accessed August 5, 2025, https://www.reddit.com/r/gameenginedevs/comments/1789f54/why_specifically_are_kd_trees_preferred_in_ray/
24. Enhancing 3D Spatial Understanding in 2D Vision-Language Models via Voxel Representation - arXiv, accessed August 5, 2025, https://arxiv.org/pdf/2503.21214?
25. Large Scale 3D Modelling via Sparse Volumes, accessed August 5, 2025, https://elib.dlr.de/96351/1/FunkBoernerv1.pdf
26. Sparse voxel octree - Wikipedia, accessed August 5, 2025, https://en.wikipedia.org/wiki/Sparse_voxel_octree
27. 3D Flight Navigation Using Sparse Voxel Octrees - Game AI Pro, accessed August 5, 2025, http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter21_3D_Flight_Navigation_Using_Sparse_Voxel_Octrees.pdf
28. How to navigate Octree using morton code? - Stack Overflow, accessed August 5, 2025, https://stackoverflow.com/questions/79416702/how-to-navigate-octree-using-morton-code
29. Morton code construction procedure illustrated for the node 23, The… - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/figure/Morton-code-construction-procedure-illustrated-for-the-node-23-The-numbers-in-the_fig2_321487917
30. en.wikipedia.org, accessed August 5, 2025, [https://en.wikipedia.org/wiki/Sparse_voxel_octree#:_{:text=A%20sparse%20voxel%20octree%20(SVO,into%20an%20octree%20data%20representation.](https://en.wikipedia.org/wiki/Sparse_voxel_octree#:}:text=A sparse voxel octree (SVO,into an octree data representation.)
31. research.tudelft.nl, accessed August 5, 2025, https://research.tudelft.nl/en/publications/transform-aware-sparse-voxel-directed-acyclic-graphs#:~:text=Sparse%20Voxel%20Directed%20Acyclic%20Graphs%20(SVDAGs)%20have%20proven%20to%20be,improved%20when%20considering%20mirror%20symmetries.
32. Oasis - Info/Graphics - Refuge Studios, accessed August 5, 2025, https://oasis.refugestudios.com.au/info/graphics
33. Hybrid Voxel Formats for Efficient Ray Tracing - arXiv, accessed August 5, 2025, https://arxiv.org/html/2410.14128v1
34. Editing with the HashDAG structure. The figure illustrates the process… - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/figure/Editing-with-the-HashDAG-structure-The-figure-illustrates-the-process-at-Level-N-this_fig4_342903661
35. AcademySoftwareFoundation/openvdb: OpenVDB - Sparse volume data structure and tools, accessed August 5, 2025, https://github.com/AcademySoftwareFoundation/openvdb
36. OpenVDB, accessed August 5, 2025, https://www.openvdb.org/
37. Insight: VDB, a deep dive - JangaFX, accessed August 5, 2025, https://jangafx.com/insights/vdb-a-deep-dive
38. VDB: High-Resolution Sparse Volumes with Dynamic Topology - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/publication/259288658_VDB_High-Resolution_Sparse_Volumes_with_Dynamic_Topology
39. VDB: High-resolution sparse volumes with dynamic topology - Ken Museth, accessed August 5, 2025, https://www.museth.org/Ken/Publications_files/Museth_TOG13.pdf
40. OpenVDB Overview - OpenVDB, accessed August 5, 2025, https://www.openvdb.org/documentation/doxygen/overview.html
41. Transforms and Maps - OpenVDB, accessed August 5, 2025, https://www.openvdb.org/documentation/doxygen/transformsAndMaps.html
42. Transformation and CSG Operations on grid in OpenVDB - Stack Overflow, accessed August 5, 2025, https://stackoverflow.com/questions/35958627/transformation-and-csg-operations-on-grid-in-openvdb
43. Balance Refinement of Massive Linear Octree Datasets - CiteSeerX, accessed August 5, 2025, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=56b7794240e17ff7b9d99ba6bb851316a5b0a71c
44. Low-Cost Parallel Algorithms for 2:1 Octree Balance - p4est, accessed August 5, 2025, https://p4est.github.io/papers/IsaacBursteddeGhattas12.pdf
45. An Octree-Based Spatial Index for Space-Based Space Surveillance Coverage Volume Computation, accessed August 5, 2025, https://arc.aiaa.org/doi/pdfplus/10.2514/6.2024-1675
46. csteuer/ParallelBottomUpBalancedOctreeBuilder: A library for the parallel bottom-up creation of 2:1 balanced octrees. - GitHub, accessed August 5, 2025, https://github.com/csteuer/ParallelBottomUpBalancedOctreeBuilder
47. VoxelMap++: Mergeable Voxel Mapping Method for Online LiDAR(-inertial) Odometry | Request PDF - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/publication/372961600_VoxelMap_Mergeable_Voxel_Mapping_Method_for_Online_LiDAR-inertial_Odometry
48. New LiDAR Based SLAM Systems for Real-Time Campus Tour Robot Navigation - College of Engineering & Computer Science (CECS) - CSUN, accessed August 5, 2025, https://www.ecs.csun.edu/~av884538/publication/2024ICMI4.pdf
49. FR-LIO: Fast and Robust Lidar-Inertial Odometry by Tightly-Coupled …, accessed August 5, 2025, https://arxiv.org/abs/2302.04031
50. [2302.04031] Fast and Robust Lidar-Inertial Odometry by Tightly-Coupled Iterated Kalman Smoother and Robocentric Voxels - ar5iv, accessed August 5, 2025, https://ar5iv.labs.arxiv.org/html/2302.04031
51. FR-LIO: Fast and Robust Lidar-Inertial Odometry by Tightly-Coupled Iterated Kalman Smoother and Robocentric Voxels - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/publication/368361497_FR-LIO_Fast_and_Robust_Lidar-Inertial_Odometry_by_Tightly-Coupled_Iterated_Kalman_Smoother_and_Robocentric_Voxels
52. Voxelisation Algorithms and Data Structures: A Review - MDPI, accessed August 5, 2025, https://www.mdpi.com/1424-8220/21/24/8241
53. Foundational Models for 3D Point Clouds: A Survey and Outlook - arXiv, accessed August 5, 2025, https://arxiv.org/html/2501.18594v1